%        File: hw1.tex
% Homework 1
\documentclass[a4paper]{article}
\usepackage[hmargin=1cm,vmargin=1.5cm]{geometry}
\begin{document}
\title{Answer Set \#1}
\author{Aditya Joshi (aj7645)}
\date{}
\maketitle
\subsection*{Slip-day Status}
Slip days used (this homework): 0\indent Slip days used (total): 0
\subsection*{Answer 1}
A global state (snapshot) is consistent iff:
\begin{itemize}
    \item Every message recorded as sent in the local state of a sender process is captured
        in the state of the channel or in the state of the receiver. 
    \item For every effect, its cause is present. In other words, 
        a state including receipt of a message contains the corresponding send.
\end{itemize}
Obtaining consistent global states can be fulfilled in a non-FIFO system
by using a coloring scheme on computation messages (Lai-Yang algorithm):
\begin{enumerate}
    \item Every process is initially white (red) and turns red (white) while taking a snapshot.
    \item Every message sent by a white (red) process is colored white (red). Thus,
    a white (red) message is a message that was sent before (after) the sender
    of that message recorded its local snapshot.
    \item Every white process takes its snapshot at its convenience, but no later than
    the instant it receives a red message. Thus, when a white (red) process receives a red (white) message, 
    it records its local snapshot before processing the message. This ensures that no message sent by a
    process after recording its local snapshot is processed by the destination before the it records its local snapshot. 
    \item Every white (red) process records a history of all white (red) messages sent or received
    by it along each channel.
    \item When a process turns red (white), it sends these histories along with its snapshot
    to the initiator process that collects the global snapshot.
    \item The initiator process computes the state of a channel $C_{ij}$ (Channel between
    process $p_i$ and $p_j$) as : 
    \begin{verbatim}  
    white (red) messages sent - white (red) messages received
    \end{verbatim}
    \item The protocol can continue by the processes alternating  between the markings - red,white.
    The snapshot obtained is consistent as a white (red) message is included either
    in the snapshot of process if it receives it before taking its snapshot, or in the state of channel.
\end{enumerate}
\newpage

\subsection*{Answer 2}
For liveness the algorithm employs the use of timeouts. Assuming a synchronous system, 
a timeout at any General is interpreted as the other process (General) failing. 
Few notes on the pseudo-code:
\begin {itemize}
\item A hash (\#) signals a one line comment.
\item ``:='' is the assignment and ``='' is the comparison operator
\item A channel will suffer at most 10 message losses, so, each send(``m'') is equivalent
    to sending 11 messages at a time.
\item The (wait- on timeout) block handles timeouts!
\end{itemize}

\hrule
\begin{verbatim}
function 2attackornot2attack():
    if inp = ``not ready``:
        # waiting for a trigger from the other general
        wait:
            # obtained response
            on deliver(m):
                if m = ''yes``:
                    # got a ''yes`` from a ready general. 
                    # change state to ''ready`` and send a ''yes`` signaling confirmation and intent
                    state := ''ready``
                    send(``yes'')
                    decide(``attack'')
                fi
                if m = ``no'':
                    # got a ``no'', decide not to attack and send ACK in form on message ``no''.
                    send(``no'')
                    decide(``not attack'')
                fi
        on timeout:
        # Waited ``long enough'' for a response. Assume other general is dead/crashed
            send(``no'')
            decide(``not attack'')
    fi
    if inp = ``ready'':
        # ``ready''  general proactively send a ``yes''
        send(``yes'')
        wait:
            on deliver(m):
                # receives a response from the other
                if m = ``yes'':
                    # both sent a ``yes'', so attack.
                    decide(``attack'')
                fi
                fi m = ``no'':
                    # negative response from other general, decide ``not attack''
                    decide(``not attack'')
        on timeout:
            # Waited ``long enough'' for a response. Assume other general is dead/crashed
            send(``no'')
            decide(``not attack'')
    fi        
\end{verbatim}
\hrule

The proposed algorithm satisfies the required criteria as follows:
\begin{itemize}
    \item Agreement - At all times the generals arrive on the same decision. A two phased 
        protocol ensures that each general gets to know of the other's intent. In case both timeout
        then they decide ``not attack''. Also as after the channel message loss threshold of 10
        messages the processes know that their responses will reach the other. So a process sending
        a ``no'' can safely assume the other process will also decide ``not attack''.
    \item Validity - If both inputs are ``not ready'' then both the Generals will timeout, send a ``no''
        and decide not to attack. Similarly, if both inputs are ``ready'' then both Generals would
        send a ``yes'' and decide to ``attack''.
    \item Termination - Every General eventually decides as in case both timeout waiting for 
        each other, they simply decide ``not attack'' and stop. Also, sending $m$ copies of each message,
        where $m$ = channel failure (here, 10) threshold + $1$, ensures that responses will eventually be received
        and acted on.

\end{itemize}


\subsection*{Answer 3}
The global snapshot with multiple initiators can be obtained in two phases. 
Phase 1 includes recording the snapshot locally at every process and Phase 2 deals
with distributing the global snapshot to all initiators. Even though there are multiple 
initiators processes need to take only one snapshot.\\
Multiple initiator snapshot protocol (Spezialetti-Kearns):
\begin{itemize}
    \item Each process $p_i$ maintains a variable $init_i$ to keep track of
   the initiator of the algorithm. 
   \item When a process receives the "take snapshot now" message, it records the 
    initiator's identifier carried in the message in $init$ . The initiator
   records its own identifier in $init$.
   \item A region holds all the processes whose $init$ field contains the same initiator. 
   With multiple concurrent initiators, the system gets partitioned into multiple regions.
    \item When a process receives a "take snapshot now" message with an initiator’s identifier 
        different from the value in $init$, a concurrent initiation of the
   algorithm is detected and the new initiator lies in a different region.
   The identifier of the concurrent initiator is recorded in a local set variable $otherInit$. 
  \item  Though $snapshot$ requests arrive at a node contain
   identifiers of different initiators, they are considered part of the same instance
   of the algorithm for the purpose of channel state recording. So multiple snapshots are not taken.
    \item Snapshot recording at a process is complete after it has received a $snapshot$
        request along each of its channels. After every process has recorded its snapshot,
   the system is partitioned into as many regions as the number of concurrent
   initiations of the algorithm. The variable $otherInit$ set at a process contains
   the identifiers of the neighboring regions.

\end{itemize}

   The initiator assembles the snapshot as follows: 
   \begin{itemize}
   \item The initiator of the algorithm is the root of a spanning tree and all processes in its 
       region belong to its spanning tree. 
   \item The process contained in $init_i$ is the parent of $p_i$ in the spanning
   tree. When a leaf process in the spanning tree has recorded the states of all
   incoming channels, the process sends the locally recorded state $(LocalSnapshot, otherInit)$ 
   to its parent in the spanning tree. 
     \item When the initiator receives the locally recorded states of all its descendants
   from its children processes, it assembles the snapshot for all the processes in
   its region and the channels incident on these processes. 
   \item The initiator knows the identifiers of initiators in adjacent regions using $otherInit$ information it
   receives from processes in its region. 
   \item The initiator exchanges the snapshot of
   its region with the initiators in adjacent regions in rounds. 
   \item In each round, an initiator sends to initiators in adjacent regions, any new information obtained
   from the initiator in the adjacent region during the previous round of message
   exchange. 
   \item A round is complete when an initiator receives information, or the
   blank message (signifying no new information will be forthcoming) from all
   initiators of adjacent regions.
   \end{itemize}

\subsection*{Answer 4}
All-to-all causal delivery can be implemented using a causal broadcast protocol (Raynal-Schiper-Toueg)
employing a message counting and control matrix technique.
To implement the protocol, every site in system has control information representing the
site’s perception of the system state. This information allows each site to decide when a
received message can be delivered to the system. Additionally, information is added to
every message delivered, so that the receiving process can update its perception of the
state of the system.
The protocol works as follows:
\begin{itemize}
\item Every site in the system manages the following two
variables: $DELIV$ and $SENT$ (which contains control information). On process $p_i$, the
variable $DELIV_i[j]$ represents the number of messages sent from $p_j$ and delivered to $p_i$;
the variable $SENT_i[k,l]$ represents the knowledge of $p_i$ of the number of messages sent
(but not necessarily delivered) from $p_k$ to $p_l$.
\item The behavior of $p_i$ is expressed by the following rules governing the sending
and receiving of a message in the system:
\begin{enumerate} 
    \item When a message $M$ is sent from $p_i$ to $p_j$, $M$ is sent together with a copy of the $SENT$
        variable.
    \item    $p_i$ increments $SENT$:
                Send $(M,SENT)$ to $S_j$
                $SENT_i[i,j]$ := $SENT_i[i,j] + 1$
     \item A message $M$ sent by $p_j$ can be delivered to $p_i$ only if $DELIV_i[k] >= SENT_j[k,i]$.
         That is, if the number of messages delivered from $p_k$ to $p_i$ is equal to or more than the 
         $p_i, p_k$ information with $p_j$ as revealed by $SENT_j$.
 \end{enumerate}
\item Once a message has been delivered, the site's perception of the state of the system is
updated. This way each site now has the global perception and causal ordering of messages.
\end{itemize}
\subsection*{Answer 5}
Consider a set of n process $p_1,..,p_n$ where $e^{k}_{i}$ is the $k^{th}$ event of process $p_i$.
Let, $\sigma^{k}_{i}$ be the local state of process $p_i$ after having executed event $e^{k}_{i}$.
Each consistent cut corresponds to a consistent global state.\\


The vector clock for $p_i$, $VC(e_k)[1..n]$ , just after $e^{k}_{i}$ has been executed will contain 
the number of events of all the process which have causally preceded $e^{k}_{i}$. 
So, $\Sigma_{min}(\sigma_{k}^{i})$, which is the consistent global state
with the smallest level containing  $\sigma_{k}^{i}$, will be obtained by a consistent cut with $\sigma_{k}^{i}$
at its frontier. The consistent cut, $(c_1,..,c_n)$, in question is the same which has the events in its frontier as 
given by the vector clock of  $\sigma_{k}^{i}$. Therefore, $\forall j: c_j =  VC(e_k)[j]$ where $j \in (1,n)$ 


\end{document}


